HW#3 --- last modified February 06 2019 04:20:31..

Solution set.

Due date: Apr 6

Files to be submitted:
  Hw3.zip

Purpose:

Related Course Outcomes:

LO4 -- Analyze the correctness and run time of a distributed algorithm

The main course outcomes covered by this assignment are:

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw2.zip file. The written part should be in a file Hw2.pdf. For the written part of the homework you should write solutions f or the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.

1. Modify the Async-CPP algorithm so that it works if there were three processors and three registers.
2. Modify the ByzGen algorithm so as to make it work for as large a value `t` of fault processors possible. Determine `t` in terms of `n`.
3. Carefully give a DMRC algorithm for computing `A^2` where `A` is an `n times n` matrix. Assume the input consist of (key; value) pairs of the form `((i,j); a_(i,j))` where the key is the pair `(i,j)` and the value is the `(i,j)` entry in `A`.
4. Let `k` be the size of our cache. Let `R` be any request sequence. Prove `F_(FIFO)(R) leq k cdot F_(MIN)(R)+k`.

For the coding part of the assignment I would like to code the Parallel MIS algorithm using Java threads. Your program will be tested from the command line as follows:

javac ParallelMIS.java
java ParallelMIS graph_file

Here graph_file will be a file containing the adjacency matrix of a graph you want to find a maximal independent set for. This will be written as a series of rows of 1's and 0's separated by spaces, `(i, j)` is 1 if there is an edge shared by `i` and `j`. As the graph is undirected it is symmetric. For example, the graph, in this lecture slide would be expressed as (I substracted 1 off each vertex name):

0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 0 1 0
1 0 0 0 1 0
0 0 1 1 0 1
0 0 0 0 1 0

On such an input your program should output a maximal independent set. For example, on the above input it might output:

0
2
5

Each vertex in the independent set is listed on its own line from least to greatest. Again, I substracted 1 off each vertex names I used on the slide.

Point Breakdown